package org.example.myleet.p1584;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    /**
     * 35 ms
     * O(n^n)
     * Prim算法
     * 从点的角度利用贪心的方式维护最小的cost
     */
    public int minCostConnectPoints(int[][] points) {
        if (points.length < 2) {
            return 0;
        }
        //待加入图中的节点
        List<Point> v = new ArrayList<>(points.length);
        //已经加入图中的节点
        List<Point> vNew = new ArrayList<>(points.length);
        for (int i=0; i<points.length; i++) {
            //初始化所有的点
            v.add(new Point(points[i]));
        }
        //先将第一个点加入到图中
        vNew.add(v.remove(0));
        int totalCost = 0;
        while (!v.isEmpty()) {
            int removeIdx = 0, minCost = Integer.MAX_VALUE;
            for (int i=0; i<v.size(); i++) {
                //更新待加入图中的节点离图中新加入的节点的最小距离，之前加入过图中的节点会已经计算过距离，所以只要计算最新加入的一个就可以了
                v.get(i).cost = Math.min(v.get(i).cost, manhattanDistance(v.get(i), vNew.get(vNew.size()-1)));
                if (minCost > v.get(i).cost) {
                    //如果发现新的加入图最小代价的节点，则标记为待加入节点
                    removeIdx = i;
                    minCost = v.get(i).cost;
                }
            }
            //从v中移除要加入图的节点，加入到vNew中，并累加cost
            vNew.add(v.remove(removeIdx));
            totalCost += minCost;
        }
        return totalCost;
    }

    static int manhattanDistance(Point p1, Point p2) {
        return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
    }

    static class Point {
        int x;
        int y;
        int cost;

        public Point(int[] p) {
            x = p[0];
            y = p[1];
            cost = Integer.MAX_VALUE;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Point{");
            sb.append("x=").append(x);
            sb.append(", y=").append(y);
            sb.append('}');
            return sb.toString();
        }
    }
}
